# -*- coding: utf-8 -*-

"""剑指 Offer II 022. 链表中环的入口节点
给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。

示例 1：
输入：head = [3,2,0,-4], pos = 1
(3) --> (2) --> (0) --> (-4)
(-4) --> (2)

输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：
输入：head = [1,2], pos = 0
(1) --> (2)
(2) --> (1)

输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：
输入：head = [1], pos = -1
(1)

输出：返回 null
解释：链表中没有环。 

提示：
链表中节点的数目范围在范围 [0, 10^4] 内
-10^5 <= Node.val <= 10^5
pos 的值为 -1 或者链表中的一个有效索引"""

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    """本题解法，是令人振奋的一次双指针想法。
    环检测，用快慢指针是毫无疑问可以实现的。
    但是入环节点呢？此时换个想法就很关键了，首先，快慢指针相遇的节点，肯定在环里面；
    此时，不妨换一个结构考虑问题，在相遇节点 fixed 之后将环剪断，那么链表就成了一个枝丫状，在入环节点处汇合，终结于 fixed 节点。
    那么，将两个枝丫再剪成等长的，用两个指针从枝丫尖往 fixed 走，汇合点不就是入环节点了吗？
    
    提交之后，执行用时超过96.00%"""
    def detectCycle(self, head: ListNode) -> ListNode:
        try:
            """快慢指针环检测，定点 fixed """
            slow, quick = head.next, head.next.next
            while True:
                if slow is quick:
                    fixed = slow
                    break

                if (not slow) or (not quick):
                    return
                
                slow = slow.next
                quick = quick.next.next

            """枝丫AB，长度计算"""
            branchA, branchB = head, fixed.next
            stepA, stepB = 0, 0
            while True:
                if branchA is fixed:
                    break
                branchA = branchA.next
                stepA += 1
            while True:
                if branchB is fixed:
                    break
                branchB = branchB.next
                stepB += 1
            
            """枝丫AB等长处理"""
            branchA, branchB = head, fixed.next
            if stepA > stepB:
                while True:
                    if stepA == stepB:
                        break
                    branchA = branchA.next
                    stepA -= 1
            elif stepB > stepA:
                while True:
                    if stepB == stepA:
                        break
                    branchB = branchB.next
                    stepB -= 1
            
            """从枝丫往 fixed 走，到汇合点就是入环节点"""
            while True:
                if branchA is branchB:
                    return branchA
                branchA = branchA.next
                branchB = branchB.next
        except AttributeError:
            return


if __name__ == '__main__':
    head = ListNode(3)
    head.next = ListNode(2)
    head.next.next = ListNode(0)
    head.next.next.next = ListNode(-4)
    head.next.next.next.next = head.next
    so = Solution()
    print(so.detectCycle(head))

    head = ListNode(1)
    head.next = ListNode(2)
    head.next.next = head
    print(so.detectCycle(head))

    head = ListNode(1)
    print(so.detectCycle(head))
